import java.util.Scanner;

public class Main {
    private static int[] next;
    private static String hostStr;
    private static String matchingStr;
    //创建 next 数组
    public static void createNext(){
        //创建数组
        next = new int[matchingStr.length()];
        //将第一个值设为0,因为第一个字符是表头
        next[0] = 0;
        int j = 0;
        for(int i = 1; i < matchingStr.length(); i++){
            //如果不匹配,向前找可以跳过的字符数
            while(j > 0 && matchingStr.charAt(i) != matchingStr.charAt(j)){
                j = next[j-1];
            }
            //如果匹配, 则j++, j 表示匹配相同的长度
            if(matchingStr.charAt(i) == matchingStr.charAt(j)){
                j++;
            }
            //next[i] 表示该下标已经匹配到的字符长度
            next[i] = j;
        }
    }

    public static void matching(){
        int j = 0;
        for(int i = 0; i < hostStr.length(); i++){
            if(hostStr.charAt(i) == matchingStr.charAt(j)){
                j++;
            }
            else{
                j = next[j];
            }
            if(j == matchingStr.length()){
                System.out.println(i-6);
                j = next[j-1];
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入主字符串:");
        hostStr = scanner.next();
        System.out.println("请输入要匹配的字符串:");
        matchingStr = scanner.next();
        //创建 next 数组
        createNext();
        //子字符串匹配
        matching();
    }
}